package morris

import "fmt"

func MorrisPre(head *Node){
	cur := head
	//fmt.Println(cur)
	for cur != nil {
		if cur.Left != nil {
			mostRight := GetMostRight(cur.Left, cur)
			if mostRight.Right == cur {
				mostRight.Right = nil
				cur = cur.Right
			} else if mostRight.Right == nil {
				mostRight.Right = cur
				fmt.Println(cur.Val)
				cur = cur.Left
			}
		} else {
			fmt.Println(cur.Val)
			cur = cur.Right
		}
	}
}


func MorrisPre1(head *Node){
	cur := head
	var mostRight *Node
	for cur != nil {
		mostRight = cur.Left
		if mostRight != nil { // 存在左节点的节点会回到自身两次
			for mostRight.Right != nil && mostRight.Right != cur {
				mostRight = mostRight.Right
			}
			if mostRight.Right == nil {
				// 可以回到自身节点的节点，在第一次到达时，直接打印
				fmt.Println(cur.Val)
				mostRight.Right = cur
				cur = cur.Left
				continue
			}
			mostRight.Right = nil
		} else { // 不存在左节点回不到自身，直接打印
			fmt.Println(cur.Val)
		}
		cur = cur.Right
	}
}